﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <algorithm>
#include <ios>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

void quickSort(vector<int>& arr, int left, int right)
{
    if (left >= right) return;

    int mid = left + (right-left) / 2;
    swap(arr[mid], arr[left]);
    int target = arr[left];

    // 1 0 2 3 5
    int li = left, ri = right, i = left;
    while (li < ri&&i <= ri)
    {
        if (arr[i] < target) swap(arr[li++], arr[i++]);
        else if (arr[i] == target) i++;
        else swap(arr[i], arr[ri--]);
    }

    quickSort(arr, left, li-1);
    quickSort(arr, li+1, right);
}

int main(int argc, char* argv[])
{

    vector<int> arr = { 1 , 2 , 6 , 3 ,9 ,10 ,7 ,7 ,6 ,3,2,0 };
    cout << "排序前的数组: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    quickSort(arr, 0, arr.size() - 1);

    cout << "排序后的数组: ";
    for (int num : arr) {
        cout << num << " ";
    }
}
// 64 位输出请用 printf("%lld")
//1 1 1
//1 0 0
//1 0 0
//1 0 0